题解 CF555E 【Case of Computer Network】

发表于 | 更新于

$Description$

给定一个$n$个点$,m$条边的无向图。有$q$条有向路线分别从$s_i$到达$t_i$。 现在你要给无向图的每条边分配一个方向。问是否存在一种分配答案使得每条路线的$s_i$和$t_i$都满足能够从$s_i$走到$~t_i$。

$Solution$

很容易想到将这个无向图进行边双缩点

考虑边双性质:同一边双联通分量的任意两点至少存在两条不存在同一条边的路径。

所有每对于一个边双，它内部的边一定可以通过分配方向来使得每对点之间都可以互相走到。

缩点后原图就变成了一个森林(原图可能不是一个连通图)。

对于森林中的每一个点，把在同一个树上的所有点用并查集并起来，最后查询时如果有一条线路中的$s_i$和$t_i$不在一棵树上，那么就输出$No$

我们可以对每个点$u$维护两个标记$up$和$down,$表示$u-fa$这条边的方向是$u\rightarrow fa(up)$还是$u\leftarrow fa(down)(fa$是$u$的父亲$)$如果一个节点同时拥有两个标记则无解。

先考虑暴力实现$:$将$s_i$到$lca$的路径上$($不包括$lca)$的点打上一个$up$的标记,将$lca$到$t_i$的点打上一个$down$的标记$($不包括$lca)$

我们发现这个东西显然是可以用树上差分优化的

关于树上差分的实现$:$将$s_i$的$up$标记打上一个$+1$,$t_i$的$down$标记上打上一个$+1$标记,在$lca$的$up$和$down$的标记分别打上一个$-1$标记。最后只需在树遍历回溯时加上子节点的标记并判断是否有一个点同时拥有两个标记即可

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define re register
#define N 400203
using namespace std;
struct edge{
    int dis,to,next;
}e[N];
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int vis[N],dep[N],fa[N],f[N][23],num,n,m,c[N],col,up[N],dn[N],q,u[N],v[N],cnt=1,head[N],dfn[N],low[N],st[N],top;
int find(int k){
    return fa[k]==k?k:fa[k]=find(fa[k]);
}
inline void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}    
void Tarjan(int u){
    dfn[u]=low[u]=++num;
    st[++top]=u;
    for (int i=head[u];i;i=e[i].next){        
        int v=e[i].to;
        if (vis[i])continue;
        vis[i]=vis[i^1]=1;
        if (!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if (!c[v])
            low[u]=min(low[u],dfn[v]);
    }
    if (dfn[u]==low[u]){
        ++col;
        do{
            c[st[top--]]=col;
        }while (st[top+1]!=u);
    }
}
void dfs1(int u,int fa){
    f[u][0]=fa;dep[u]=dep[fa]+1;
    for (int i=1;i<=20;++i)
        f[u][i]=f[f[u][i-1]][i-1];
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if (v==fa)continue;
        dfs1(v,u);
    }
}
void dfs(int u,int fa){
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if (v==fa)continue;
        dfs(v,u);
        up[u]+=up[v];dn[u]+=dn[v];
    }
    if (up[u]&&dn[u]){puts("No");exit(0);}
}
int LCA(int x,int y){
    if (dep[x]<dep[y])swap(x,y);
    for (int i=20;i>=0;--i){
        if (dep[f[x][i]]>=dep[y])x=f[x][i];
        if (x==y)return x;
    }
    for (int i=20;i>=0;--i)
        if (f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
signed main(){
    n=read(),m=read(),q=read();
    for (int i=1;i<=m;++i){
        u[i]=read(),v[i]=read();
        add(u[i],v[i]);add(v[i],u[i]);
    }
    for (int i=1;i<=n;++i)
        if (!dfn[i])
            Tarjan(i);
    memset(head,0,sizeof(head));cnt=1;
    for (int i=1;i<=col;++i)fa[i]=i;
    for (int i=1;i<=m;++i)
        if (c[u[i]]!=c[v[i]])
            add(c[u[i]],c[v[i]]),add(c[v[i]],c[u[i]]),fa[find(c[u[i]])]=find(c[v[i]]);
    for (int i=1;i<=col;++i)
        if (!dep[i])
            dfs1(i,0);
    while (q--){
        int s=c[read()],t=c[read()],lca=LCA(s,t);
        if (s==t)continue;
        if (find(s)!=find(t)){puts("No");return 0;}
        --up[lca];++up[s];--dn[lca];++dn[t];
    }
    for (int i=1;i<=col;++i)
        if (find(i)==i)
            dfs(i,0);
    puts("Yes");
    return 0;
}